#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
#include <pthread.h>
#include <assert.h>
#include <limits.h>

#define N 2
int a[] = {5, 11, 0, 92, 54, 37, 11, 27, 11, 52};
int step;

void* selection_sort(void* arg)
{
    int* p = arg;
    int begin = *p * step;

    int end = begin+step;
    int min, pos, j;
    for (int i = begin; i < end; i++)
    {
        min = INT_MAX;
        pos = i;
        for (j = i; j < end; j++)
        {
            if (a[j] < min)
            {
                min = a[j];
                pos = j;
            }
        }
        int tmp = a[i];
        a[i] = a[pos];
        a[pos] = tmp;
    }

    return NULL;
}

int main(int argc, char** argv)
{
    assert(argc == 1);
    int len = sizeof(a) / sizeof(int);
    step = len/N;
    
    int array[N];
    for (int i = 0; i < N; i++)
        array[i] = i;

    printf("a[] = ");
    for (int i = 0; i < len; i++)
        printf("%d ", a[i]);
    printf("\n");

    pthread_t worker[N];
    for (int i = 0; i < N; i++)
        pthread_create(worker+i, NULL, selection_sort, array+i);

    for (int i = 0; i < N; i++)
        pthread_join(worker[i], NULL);

    //merge sort
    int i = 0;
    int j = step;
    int b[len], k = 0;
    printf("step = %d\n", step);
    printf("len = %d\n", len);

    while (i < step && j < len)
    {
        while (i < step && a[i] <= a[j])
            b[k++] = a[i++];
        while (j < len && a[j] <= a[i])
            b[k++] = a[j++];
    }

    if (i < step)
        memcpy(b+k, a+i, (step-i)*sizeof(int));
    if (j < len)
        memcpy(b+k, a+j, (len-j)*sizeof(int));
    
    printf("b[] = ");
    for (int i = 0; i < len; i++)
        printf("%d ", b[i]);
}